package com.chentf.algorithm.algorithm.StringAndArrays;

/**
 * @author chentengfei
 * @desc 合并两个有序链表
 * @date 2022-01-10 21:56:14
 */
public class MergeTwoLists {
    /***
     *将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
     * 示例 1:
     * 输入：l1 = [1,2,4], l2 = [1,3,4]
     * 输出：[1,1,2,3,4,4]
     * 示例 2：
     * 输入：l1 = [], l2 = []
     * 输出：[]
     * 示例 3：
     * 输入：l1 = [], l2 = [0]
     * 输出：[0]
     */
    /***
     *递归解法
     * 根据以上规律考虑本题目：
     * 终止条件：当两个链表都为空时，表示我们对链表已合并完成。
     * 如何递归：我们判断 l1 和 l2 头结点哪个更小，然后较小结点的 next 指针指向其余结点的合并结果。（调用递归）
     */
    public static ListNode mergeTwoLists(ListNode l1,ListNode l2){
        if(l1 == null){
            return l2;
        }else if(l2 == null){
            return l1;
        }else if(l1.val < l2.val){
            l1.next = mergeTwoLists(l1.next,l2);
            return l1;
        }else{
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(2);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(3);
        ListNode l2 = new ListNode(5);
        l2.next = new ListNode(6);
        l2.next.next = new ListNode(4);
        ListNode listNode = mergeTwoLists(l1, l2);
        ListNode node = listNode;
        while (node!=null){
            if (node.next==null){
                System.out.print(node.val );
                node = node.next;
            }else{
                System.out.print(node.val + "->");
                node = node.next;
            }
        }
    }
}
